package com.LeeCode;

/**
 * 字符至少出现 K 次的子字符串 I
 */

public class Code3325 {
    public static void main(String[] args) {
        String s = "abcde";
        int k = 1;
        System.out.println(new Code3325().numberOfSubstrings(s, k));
    }

    public int numberOfSubstrings(String s, int k) {
        int ans = 0, right = 0, n = s.length(), count = 0;
        int[] cnt = new int[26];
        char[] chars = s.toCharArray();

        for (int left = 0; left < n; left++) {
            while (right < n && count < 1) {
                cnt[chars[right] - 'a']++;
                if (cnt[chars[right] - 'a'] == k) count++;
                right++;
            }

            if (count >= 1)
                ans += n - right + 1;

            cnt[chars[left] - 'a']--;
            if (cnt[chars[left] - 'a'] == k - 1) count--;
        }
        return ans;
    }
}
